package _11_整理题目._1_链表指针._删除节点;

import org.junit.Test;
import util.ListNode;

/**
 * 给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针
 * 例如，
 * 给出的链表为: 1 2 3 4 5  n = 2.
 * 删除了链表的倒数第 n 个节点之后,链表变为 1 2 3 5.
 * 
 * 由于可能删除第一个节点，所以需要一个 fake 节点连接 head，再快慢指针
 * 删除第 k 个节点，需要找到 k 节点前面那个节点，改变它的 next 连接即可
 *
 * https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
 *
 * 思路1 先遍历长度，计算要删除的位置
 * 思路2 压栈，弹出第 n 个
 * 思路3 快慢指针
 */
public class _04_删除链表的倒数第n个节点 {
    
    public ListNode removeNthFromEnd (ListNode head, int n) {
        ListNode fake = new ListNode(0);
        fake.next = head;
        ListNode fast = fake;
        ListNode slow = fake;
        
        while (n > -1) {
            if (fast == null) return null;
            fast = fast.next;
            n--;
        }
        
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return fake.next;
    }
    
    @Test
    public void main() {
        Integer[] array = {1,2,3,4,5};
        ListNode head = ListNode.getListFromArray(array);
        ListNode.printList(head);
        ListNode result = removeNthFromEnd(head, 3);
        ListNode.printList(result);
    }
    
}
